#include"BinaryTree.h"
#include"Queue.h"


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    if ((*pi) == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    root->data = a[(*pi)++];
    root->left = BinaryTreeCreate(a, n, pi);
    root->right = BinaryTreeCreate(a, n, pi);

    return root;
}
//二叉树的销毁
void DestroyTree(BTNode** root)
{
    if (*root)
    {
        DestroyTree(&(*root)->left);
        DestroyTree(&(*root)->right);
        free(*root);
        *root = NULL;
    }
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    assert(k > 0);
    if (root == NULL)
        return 0;
    if (k == 1) 
        return 1;
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;
    // BTNode* ret1=BinaryTreeFind(root->_left,x);
    // if(ret1)
    //     return ret1;
    // BTNode* ret2=BinaryTreeFind(root->_right,x);
    // if(ret2)
    //     return ret2;
    // return NULL;
    return BinaryTreeFind(root->left, x) || BinaryTreeFind(root->right, x);
}
//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
        return NULL;
    //根 -> 左子树 -> 右子树
    printf("%d ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
        return NULL;
    //左子树 -> 根 -> 右子树
    BinaryTreeInOrder(root->left);
    printf("%d", root->data);
    BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
        return NULL;
    //左子树 -> 右子树 -> 根
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%d", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	int BinaryTreeLevelKSize= 1;
	while (!QueueEmpty(&q))
	{
		// 一层一层出
		while (BinaryTreeLevelKSize--)
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);

			printf("%d ", front->data);

			if (front->left)
				QueuePush(&q, front->left);
			if (front->right)
				QueuePush(&q, front->right);
		}
		printf("\n");
		BinaryTreeLevelKSize= QueueSize(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	int BinaryTreeLevelKSize = 1;
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	// 前面遇到空以后，后面还有非空就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
